package com.github.yangyishe.p500;

import java.util.*;

/**
 * 433. 最小基因变化
 * https://leetcode.cn/problems/minimum-genetic-mutation/description/?envType=study-plan-v2&envId=top-interview-150
 *
 * 基因序列可以表示为一条由 8 个字符组成的字符串，其中每个字符都是 'A'、'C'、'G' 和 'T' 之一。
 *
 * 假设我们需要调查从基因序列 start 变为 end 所发生的基因变化。一次基因变化就意味着这个基因序列中的一个字符发生了变化。
 *
 * 例如，"AACCGGTT" --> "AACCGGTA" 就是一次基因变化。
 * 另有一个基因库 bank 记录了所有有效的基因变化，只有基因库中的基因才是有效的基因序列。（变化后的基因必须位于基因库 bank 中）
 *
 * 给你两个基因序列 start 和 end ，以及一个基因库 bank ，请你找出并返回能够使 start 变化为 end 所需的最少变化次数。如果无法完成此基因变化，返回 -1 。
 *
 * 注意：起始基因序列 start 默认是有效的，但是它并不一定会出现在基因库中。
 *
 *
 *
 * 示例 1：
 *
 * 输入：start = "AACCGGTT", end = "AACCGGTA", bank = ["AACCGGTA"]
 * 输出：1
 * 示例 2：
 *
 * 输入：start = "AACCGGTT", end = "AAACGGTA", bank = ["AACCGGTA","AACCGCTA","AAACGGTA"]
 * 输出：2
 * 示例 3：
 *
 * 输入：start = "AAAAACCC", end = "AACCCCCC", bank = ["AAAACCCC","AAACCCCC","AACCCCCC"]
 * 输出：3
 *
 *
 * 提示：
 *
 * start.length == 8
 * end.length == 8
 * 0 <= bank.length <= 10
 * bank[i].length == 8
 * start、end 和 bank[i] 仅由字符 ['A', 'C', 'G', 'T'] 组成
 */
public class Problem433 {
    public static void main(String[] args) {
        String start = "AAAAACCC", end = "AACCCCCC";
        String[]bank = new String[]{"AAAACCCC","AAACCCCC","AACCCCCC"};

        Problem433 problem433 = new Problem433();
        int i = problem433.minMutation(start, end, bank);
        System.out.println(i);
    }

    /**
     * 思路:
     * 模型创建-可将每个基因序列,认为是一个节点.
     * 开始,结束,及基因库中的所有基因, 构成了节点的集合.
     * 各个节点之间,如果仅有一个字符的差别,则代表两个节点之间可以关联.
     * 如此, 就构建了一个无向图.
     * 图的存储方式,可考虑使用一个string2stringSetMap的方式存储
     *
     * 问题就变成了从开始节点以最快的步骤找到结束节点.
     *
     * 从开始节点找到到结束节点的最快路径,使用广度优先遍历.
     * 每遍历一个节点,使用一个map记录到达这个节点的最小步数.
     * 遍历所有后, 拿到endGene对应的最小步数,即是结果
     *
     * @param startGene
     * @param endGene
     * @param bank
     * @return
     */
    public int minMutation(String startGene, String endGene, String[] bank) {
        geneGraph.put(startGene,new ArrayList<>());
        for (String s : bank) {
            List<String> linkGeneList=new ArrayList<>();
            for (String s1 : geneGraph.keySet()) {
                if(isLink(s,s1)){
                    linkGeneList.add(s1);
                }
            }
            geneGraph.put(s,linkGeneList);
            for (String s1 : linkGeneList) {
                geneGraph.get(s1).add(s);
            }
        }
        if(geneGraph.containsKey(endGene)){
            iterateGene(startGene,endGene,1);
            Integer minStep = minReachMap.get(endGene);
            return minStep!=null?minStep:-1;
        }else{
            return -1;
        }
    }

    private Map<String, List<String>> geneGraph=new HashMap<>();

    private boolean isLink(String gene1,String gene2){
        int differSize=0;
        for(int i=0;i<8;i++){
            if(gene1.charAt(i)!=gene2.charAt(i)){
                differSize++;
            }
            if(differSize>1){
                return false;
            }
        }
        return differSize==1;
    }

    private Map<String,Integer> minReachMap=new HashMap<>();

    private void iterateGene(String startGene,String endGene,int currentStep){
        if(startGene.equals(endGene)){
            return;
        }
        List<String> linkGeneList = geneGraph.get(startGene);
        List<String> canTouchGeneList=new ArrayList<>();
        for(String s:linkGeneList){
            boolean canTouch=touchGene(s,currentStep);
            if(canTouch){
                canTouchGeneList.add(s);
            }
        }
        for(String s:canTouchGeneList){
            iterateGene(s,endGene,currentStep+1);
        }
    }

    private boolean touchGene(String gene,int currentStep){
        if(minReachMap.get(gene)==null||minReachMap.get(gene)>currentStep){
            minReachMap.put(gene,currentStep);
            return true;
        }else{
            return false;
        }
    }
}
